package com.lijing.uniqueBinarySearchTree;

/**
 * @Description TODO
 * @title: UniqueBinarySearchTree
 * @Author LiJing
 * @Date: 2021/4/69:23 下午
 * @Version 1.0
 */
public class UniqueBinarySearchTree {
    public static void main(String[] args) {
        int n = 3;
        System.out.println(getBinarySearchTreeNum(n));
    }

    public static int getBinarySearchTreeNum(int n){
        /*
         * @Date: 2021/4/6 9:24 下午
         * Step 1: 确定状态
         * dp[i]表示1，2...i个节点组成的二叉树的种类
         */
        int[] dp = new int[n+1];
        /*
         * @Date: 2021/4/6 9:26 下午
         * Step 2: 状态转移方程，初始化
         * dp[i] += dp[j-1]dp[i-j],对于i为头节点来说，下面还有i-1个节点，可分布在左和右
         */
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
}
